package com.kehao.leetcode.hard.tree_graph;


import org.junit.Test;

public class MaxPathSumSolution {
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    private TreeNode createTree(Integer[] array){
        TreeNode[] treeNodes = new TreeNode[array.length];
        for (int i = 0; i < array.length; i++) {
            if(array[i]!=null){
                treeNodes[i] = new TreeNode(array[i]);
            }
        }
        for (int i = 0; i < array.length / 2 ; i++) {
            if(2*i+1<array.length)treeNodes[i].left = treeNodes[2*i+1];
            if(2*i+2<array.length)treeNodes[i].right = treeNodes[2*i+2];
        }
        return treeNodes[0];
    }


    Integer result = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if (root==null) return 0;
        onePathSum(root);
        return result;
    }

    private int onePathSum(TreeNode root) {
        if (root==null) return 0;
        int left = Math.max(onePathSum(root.left),0);
        int right = Math.max(onePathSum(root.right),0);
        result = Math.max(result,left+right+root.val);
        return root.val+Math.max(left,right);
    }


    @Test
    public void test01(){
        Integer[] root = {1,2,3};
        TreeNode tree = createTree(root);
        int result = maxPathSum(tree);
        System.out.println(result);
    }

    @Test
    public void test02(){
        Integer[] root = {-10,9,20,null,null,15,7};
        TreeNode tree = createTree(root);
        int result = maxPathSum(tree);
        System.out.println(result);
    }

}
